# 从上到下打印内存超限了
class Solution:
    def levelOrder(self , root ):
        # write code here
        final=[]
        if not root:
            return []
        queue = []
        queue.append(root)
        while queue:
            subs = []
            n = len(queue)
            for _ in range(n):
                node = queue.pop(0)
                # 用subs来保存每一层的节点
                subs.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            final.append(subs)
        return final

# 深度优先 根左右
def postOrder(self, root):
    if root == None:
        return
    stack=[root.val]
    res=[]
    while stack:
        cur = stack.pop()
        res.append(cur)
        if cur.left:
            stack.append(cur.left)
        if cur.right:
            stack.append(cur.right)
    while res:
        print(res.pop().val)

    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        left = 0
        mid = x // 2
        right = x
        while left <= right:
            # 二分
            mid = (left + right) // 2
            # 如果平方比x大
            if mid * mid > x:
                right = mid - 1
            # 如果平方比x小
            elif mid * mid < x:
                left = mid + 1
            else:
                return mid
        return mid
def getRoot(num):
    left = 0
    mid = num // 2
    right = num
    while left <= right:
        # 二分
        mid = (left + right) // 2
        # 如果平方比x大
        if mid * mid > num:
            right = mid - 1
        # 如果平方比x小
        elif mid * mid < num:
            left = mid + 1
        else:
            return mid
    return mid

def dfs(root):
    if root == None:
        return
    stack=[root.val]
    res=[]
    while stack:
        cur = stack.pop()
        res.append(cur)
        if cur.left:
            stack.append(cur.left)
        if cur.right:
            stack.append(cur.right)
    while res:
        print(res.pop().val)
